CodeForces978C Letters

发表于 | 更新于 | 分类于

There are dormitories in Berland State University, they are numbered with integers from to . Each dormitory consists of rooms, there are rooms in -th dormitory. The rooms in -th dormitory are numbered from to .

A postman delivers letters. Sometimes there is no specific dormitory and room number in it on an envelope. Instead of it only a room number among all rooms of all dormitories is written on an envelope. In this case, assume that all the rooms are numbered from to and the rooms of the first dormitory go first, the rooms of the second dormitory go after them and so on.

For example, in case , and an envelope can have any integer from to written on it. If the number is written on an envelope, it means that the letter should be delivered to the room number of the second dormitory.

For each of letters by the room number among all dormitories, determine the particular dormitory and the room number in a dormitory where this letter should be delivered.

Input
The first line contains two integers and — the number of dormitories and the number of letters.

The second line contains a sequence , where equals to the number of rooms in the -th dormitory. The third line contains a sequence , where equals to the room number (among all rooms of all dormitories) for the -th letter. All are given in increasing order.

Output
Print lines. For each letter print two integers and — the dormitory number and the room number in this dormitory to deliver the letter.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Examples
Input
3 6
10 15 12
1 9 12 23 26 37
Output
1 1
1 9
2 2
2 13
3 1
3 12
Input
2 3
5 10000000000
5 6 9999999999
Output
1 5
2 1
2 9999999994
Note
In the first example letters should be delivered in the following order:

the first letter in room  of the first dormitory
the second letter in room  of the first dormitory
the third letter in room  of the second dormitory
the fourth letter in room  of the second dormitory
the fifth letter in room  of the third dormitory
the sixth letter in room  of the third dormitory

解析：

题意: 查询m个数分别在一个有n个元素的递增序列中的相对位置。

两种解法：
    暴力解法为两层嵌套循环，时间复杂度为O(m×n)；
    二分法查找，时间复杂度为O(m×log2n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <stdio.h>
#define MAXN 2048 //定义一个数组的大小

// 暴力求解
int letters(int* a, int* b, int n, int m)
{
    int i, j, t, sum=0;
    
    for(j = 0; j < m; j++)
    {
        sum = 0;
        for(i = 0; i < n; i++)
        {
            sum += a[i];
            if(b[j] <= sum)
            {
                t = sum - a[i];
                printf("%d %d\n", i+1, b[j] - t);
                break;
            }
        }
    }
    
    return 0;
}

// 二分法
int binary_letters(int* a, int* b, int n, int m)
{
    int sum[MAXN] = {0};
    int i, j, r, l, mid;
    
    sum[0] = a[0];

    // 构建ai序列
    for(i = 1; i < n; i++)
        sum[i] = sum[i-1] + a[i];

    for(j = 0; j < m; j++)
    {
        if(b[j] > sum[i-1])
        {
            printf("%d index out of bounds.\n", b[j]);
            continue;
        }
        
        for(r = n - 1, l = 0; r - l > 1; )
        {
            mid = (r + l) / 2;
            if(b[j] > sum[mid])
                l = mid;
            else
                r = mid;
        }
        
        if(b[j] > sum[l])
            printf("%d %d\n", l+2, b[j]-sum[l]);
        else
            printf("%d %d\n", l+1, b[j]);
    }
    
    return 0;
}

int main()
{
    int a[] = {10, 15, 12, 12, 12};
    int b[] = {1, 9, 12, 23, 26, 37, 50, 62};

    int n = sizeof(a) / sizeof(int);
    int m = sizeof(b) / sizeof(int);

    letters(a, b, n, m);
    printf("================\n");
    binary_letters(a, b, n, m);
    
    return 0;
}

out put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1 1
1 9
2 2
2 13
3 1
3 12
5 1
================
1 1
1 9
2 2
2 13
3 1
3 12
5 1
62 index out of bounds.
0%